﻿/////////////////////////////////////////////////
//文件名:BinaryTree
//描  述:
//创建者:刘凡平(Iveely Liu)
//邮  箱:945222889@qq.com
//组  织:Iveely
//年  份:2012/5/10 14:05:09
///////////////////////////////////////////////


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Globalization;

namespace IveelySE.BigData.Common.DataStruct
{
    /// <summary>
    /// 二叉排序树
    /// </summary>
    public class BinaryTree<T>
    {
        /// <summary>
        /// 树结点
        /// </summary>
        /// <typeparam name="T">结点类型</typeparam>
        public class TreeNode<T> : IComparable, IComparable<TreeNode<T>>
        {
            #region 属性

            /// <summary>
            /// 左结点
            /// </summary>
            public TreeNode<T> Left { get; set; }
            /// <summary>
            /// 右结点
            /// </summary>
            public TreeNode<T> Right { get; set; }

            /// <summary>
            /// 父节点
            /// </summary>
            public TreeNode<T> Father { get; set; }
            /// <summary>
            /// 深度
            /// </summary>
            public int Deep { set; get; }
            /// <summary>
            /// 是否是叶子节点
            /// </summary>
            public bool IsLeaf { get; set; }
            /// <summary>
            /// 结点添加的类型
            /// </summary>
            public T Value { get; set; }

            #endregion

            #region （接口）方法

            public TreeNode()
                : this(default(T), null, null, 0)
            {

            }

            public TreeNode(T value)
                : this(value, null, null)
            {

            }

            public TreeNode(T value, TreeNode<T> Left, TreeNode<T> Right) :
                this(value, Left, Right, 1)
            {

            }

            public TreeNode(T value, TreeNode<T> Left, TreeNode<T> Right, int Deep)
            {
                this.Value = value;
                this.Left = Left;
                this.Right = Right;
                this.Deep = Deep;
                this.IsLeaf = true;
            }

            int IComparable.CompareTo(Object item)
            {
                TreeNode<T> node = item as TreeNode<T>;
                //如果比较结点为空
                if (node == null)
                {
                    throw new ArgumentException("二叉排序树结点不能为null");
                }
                else
                {
                    if (this == item)
                    {
                        return 0;
                    }
                    else
                    {
                        Comparer comparer = new Comparer(CultureInfo.CurrentCulture);
                        return comparer.Compare(this.Value, node.Value);
                    }
                }
            }

            int IComparable<TreeNode<T>>.CompareTo(TreeNode<T> item)
            {
                //如果比较结点为空
                if (item == null)
                {
                    throw new ArgumentException("二叉排序树结点不能为null");
                }
                else
                {
                    if (this == item)
                    {
                        return 0;
                    }
                    else
                    {
                        Comparer comparer = new Comparer(CultureInfo.CurrentCulture);
                        return comparer.Compare(this.Value, item.Value);
                    }
                }
            }
            #endregion
        }

        #region 变量、属性

        /// <summary>
        /// 根结点
        /// </summary>
        public TreeNode<T> Root { get; set; }
        /// <summary>
        /// 数量统计
        /// </summary>
        public int Count { get; private set; }



        /// <summary>
        /// 比较器
        /// </summary>
        private static Comparer comparer;
        /// <summary>
        /// 深度
        /// </summary>
        private int Deep { get; set; }

        #endregion

        static BinaryTree()
        {
            comparer = new Comparer(CultureInfo.CurrentCulture);
        }

        public BinaryTree()
        {
            this.Root = null;
            this.Count = 0;
            this.Deep = 0;
        }

        public BinaryTree(TreeNode<T> root)
        {
            if (root == null)
            {
                throw new ArgumentNullException("root不能为null");
            }
            this.Root = root;
            this.Count++;
            this.Deep = 1;
        }

        /// <summary>
        /// 插入结点
        /// </summary>
        /// <param name="itemValue"></param>
        public void Add(T itemValue)
        {
            //如果根结点为空
            if (this.Root == null)
            {
                //实例化
                this.Root = new TreeNode<T>(itemValue);
                //个数+1
                this.Count++;
            }
            else
            {
                TreeNode<T> iterator = this.Root;
                bool flag = true;
                int result = comparer.Compare(itemValue, iterator.Value);
                while (flag)
                {
                    if (result > 0)
                    {
                        if (iterator.Right != null)
                        {
                            iterator = iterator.Right;
                            result = comparer.Compare(itemValue, iterator.Value);
                            this.Deep++;
                        }
                        else
                        {
                            //新建右结点
                            iterator.Right = new TreeNode<T>(itemValue, null, null, this.Deep);
                            //不是叶子结点
                            iterator.IsLeaf = false;
                            //指定父节点
                            iterator.Right.Father = iterator;
                            //标志结束
                            flag = true;
                        }
                    }
                    else if (result < 0)
                    {
                        if (iterator.Left != null)
                        {
                            //转到左结点
                            iterator = iterator.Left;
                            //比较
                            result = comparer.Compare(itemValue, iterator.Value);
                            //深度+1
                            this.Deep++;
                        }
                        else
                        {
                            //新建左结点
                            iterator.Left = new TreeNode<T>(itemValue, null, null, this.Deep);
                            //那么父节点一定不是叶子结点
                            iterator.IsLeaf = false;
                            //指定父节点
                            iterator.Left.Father = iterator;
                            //个数+1
                            Count++;
                            //标记结束
                            flag = false;
                        }
                    }
                    else
                    {
                        flag = false;
                    }
                }
            }
        }

 
        /// <summary>
        /// 先序遍历
        /// </summary>
        /// <param name="root"></param>
        private void PreOrder(TreeNode<T> root)
        {
            if (root != null)
            {
                Console.WriteLine(root.Value);
                PreOrder(root.Left);
                PreOrder(root.Right);
            }
        }

        /// <summary>
        /// 先序遍历
        /// </summary>
        public void PreOrder()
        {
            this.PreOrder(this.Root);
        }


   
    }
}
